package 一些算法竞赛测试题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-01
 * Time: 13:19
 */

/*
活动选择
有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个
开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。
 */
public class Demo7 {
    private static int greedyActivitySelector(int[][] act){
        //每次选择最早结束的活动
        int len = act.length;
        int res = 1;
        int i = 0;
        for(int j = 1; j < len; j++){
            if(act[j][0] >= act[i][1]){
                i = j;
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //使用一个二维矩阵来存储每一个活动的起始时间和结束时间
        int[][] act = new int[n][2];
        for(int i = 0; i < n; i++){
            act[i][0] = scanner.nextInt();
            act[i][1] = scanner.nextInt();
        }
        //按照活动的结束时间从小到大进行排序
        Arrays.sort(act, (a, b) -> {
            return a[1] - b[1];
        });
        int res = greedyActivitySelector(act);
        System.out.println(res);
    }
}
